package q148_sortList;

import CommonClass.Common.ListNode;
class Solution_2 {
    /*
    这里直接分析效率最高的链表排序方法
    自底向上归并排序
    主要分为三个步骤
     */
    public ListNode sortList(ListNode head) {
        // 1 先判空
        if (head == null || head.next == null) {
            return head;
        }
        // 2 先遍历一次链表 求出链表的长度
        int length = 0;
        ListNode node = head;
        while (node != null) {
            length++;
            node = node.next;
        }
        // 3 将链表拆分成子链表进行排序
        // 3.1 先创建哑节点
        ListNode dummyHead = new ListNode(0, head);
        // subLength代表着子链表 初始化为1 每次将链表拆分成若干个长度为subLen的子链表 , 并按照每两个子链表一组进行合并
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            // 一个是前节点 一个是curr用来记录拆分的位置
            ListNode prev = dummyHead, curr = dummyHead.next;

            while (curr != null) {
                // 3.2 拆分subLen长度的链表-1 也就是第一个链表
                ListNode head1 = curr; // head1记录第一个链表的头
                for (int i = 1; i < subLength && curr.next != null; i++) {
                    curr = curr.next;
                }

                // 3.3 拆分第二个subLen长度的链表
                ListNode head2 = curr.next; // head2 第二个链表的头 也就是链表1尾部的下一个位置
                curr.next = null;// 此时第一个链表和第二个链表的连接被断开
                curr = head2;// 将curr移动到第二个链表的头部
                for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {
                    curr = curr.next;
                }

                // 3.4 再次断开第二个链表最后的next的链接
                // 也就是说 next将会连接到第二个链表的尾部后一个节点
                // 然后第二个链表也将断开和整个链表的连接
                ListNode next = null;
                if (curr != null) {
                    next = curr.next;
                    curr.next = null;
                }
                // 对第一个和第二个链表排序
                ListNode merged = merge(head1, head2);
                // prev的next将连接到merged后的头部节点
                prev.next = merged;
                // 然后将prev移动到merged的链表最后位置
                while (prev.next != null) {
                    prev = prev.next;
                }
                // curr来到我们断开第二个链表后的剩余链表头部位置
                curr = next;
            }
            // 注意 上方是一个循环 也就是说只要curr非空
            // while循环将会不停的将链表拆成一个和一个的节点进行merge
            // 然后结束后 for循环将会提升subLen的长度
            // 接下来while循环将会把链表拆成两个和两个的子链表进行merge
            // 每次sublen将会翻倍
        }
        return dummyHead.next;
    }

    /*
    q21 合并两个有序链表
     */
    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummyHead.next;
    }
}


